from typing import List

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        """hash
        s = set()
        for i in nums:
            if i in s:
                return i
            s.add(i)
        """
        # 数字不重复，利用数组索引
        for i in range(len(nums)):
            while i != nums[i]:                 # 如果没有归位
                if nums[i] == nums[nums[i]]:    # 并且与原位置重复，输出
                    return nums[i]
                else:                           # 否则交换位置
                    t = nums[i]
                    nums[i], nums[t] = nums[t], nums[i]

if __name__ == '__main__':
    c = Solution()
    s = [3, 4, 2, 0, 0, 1]
    print(c.findRepeatNumber(s))
        